package com.zpark;
import java.util.Arrays;
import java.util.Scanner;

/**
 * 排列
 * 复杂度：O(k * n)
 */
public class PreRange {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请指定数组的大小:");
        int n = scan.nextInt();//n表示数组大小
        //调用shuffle方法，给他数组大小，让他返回一个顺序打乱的，大小为n的数组
        int[] arr = shuffle(n);
        //输出得到的数组
        System.out.println("得到的数组为->" + Arrays.toString(arr));
        System.out.println("请输入你想得到该序列之后的第几个序列");
        int k = scan.nextInt();
        for (int i = 0; i < k; i++){
            // 调用nextPermutation()方法

            System.out.println("下" + (i + 1) + "个序列是 -> "+ Arrays.toString(nextPermutation(arr)));
        }
    }

    /**
     *得到某个序列的下一个序列
     * @param arr 原始序列
     * @return 原始序列的下一个序列
     */
    private  static int[] nextPermutation(int[] arr){
        int size = arr.length;
        int flag = arr.length - 1;
        int tmp ;
        // 从左向右找，找到相邻的两个元素，满足左边的比右边的小的那个元素
        while (flag != 0 && arr[flag - 1] > arr[flag])
            flag--;
        // 如果flag为0， 表示该序列已经是一个降序排列，那他的下一个序列是升序排列
        if (flag == 0){
            for (int i = 0; i < size / 2; i++){
                tmp = arr[i];
                arr[i] = arr[size - 1 - i];
                arr[size - 1 - i] =tmp;
            }
            return arr;
        }
        // 逆序遍历，找到比 flag - 1位置的值大的那个最小的数，与flag - 1位置的数交换
        for (int i = size - 1; i >= flag; i++){
            if (arr[i] > arr[flag - 1]){
                tmp = arr[i];
                arr[i] = arr[flag - 1];
                arr[flag - 1] =tmp;
                break;
            }
        }
        // 交换后，将flag到最右边位置的元素做升序排列
        // 注意一个问题，我们在前面已经从右向左查找过，所以应该意识到，flag到最右此时是降序
        // 拿只需将flag到最右的元素，首尾交换即可
        while (flag < size - 1){
            tmp = arr[flag];
            arr[flag] = arr[size - 1];
            arr[size - 1] =tmp;
            flag++;
            size--;
        }
        return arr;
    }
    /*
     * 生成n大小的，元素打乱的数组
     * n数组的大小
     * 打乱的数组
     */
    private static int[] shuffle(int n) {
        int[] baseArr = new int[n];
        for (int i = 0; i < n; i++) {
            baseArr[i] = i + 1;
        }
        int[] targetArr = new int[n];
        int index;
        for (int i = 0; i < targetArr.length; i++) {
            index = -1;
            do {
                index = (int) (Math.random() * n);
                targetArr[i] = baseArr[index];
                baseArr[index] = -1;
            } while (targetArr[i] == -1);
        }
        return targetArr;
    }
}
